nLab combinatorial map

Idea

A combinatorial map is a representation of a graph embedded in a surface (i.e., a topological map) as a set and a list of permutations acting on that set, with the property that two combinatorial maps are equivalent up to conjugation if and only if the corresponding graphs are isomorphic by a homeomorphism of the underlying surfaces. The precise formulation depends upon assumptions made about the underlying surface (e.g., whether it is connected and/or oriented) and about the underlying graph (e.g., whether all vertices have a fixed degree), but typically different classes of topological maps can be represented by lists of permutations satisfying different sets of constraints.

Oriented maps and hypermaps

Classical combinatorial maps

The following definition corresponds to the case which is perhaps most well-studied:

Definition

A combinatorial map $M$ is a set $D$ (whose elements are called darts) equipped with a triple of permutations $(\sigma,\alpha,\phi)$ on $D$ such that:

1. the subgroup $\langle \sigma,\alpha,\phi\rangle$ of $Aut(D)$ generated by the permutations acts transitively on $D$;

2. the composition of the permutations is the identity: $\phi\alpha\sigma = id$;

3. $\alpha$ is a fixed point-free involution.

A homomorphism of combinatorial maps

$$M \to M'$$

where $M = (D,(\sigma,\alpha,\phi)), M' = (D',(\sigma',\alpha',\phi'))$ is a function $h : D \to D'$ which commutes with each of the respective permutations,

$$h\sigma = \sigma'h \qquad h\alpha = \alpha'h \qquad h\phi = \phi' h.$$

Hence, $M$ and $M'$ are isomorphic as maps if and only there is a bijection $h : D \cong D'$ between their underlying sets of darts, such that the triple of permutations $(\sigma,\alpha,\phi)$ is mapped by conjugation along $h$ to the triple of permutations $(\sigma',\alpha',\phi')$.

In the literature, many authors equivalently define a combinatorial map by a pair $(\sigma,\alpha)$ of permutations, since by condition (2) above, the third permutation $\phi$ can always be recovered uniquely as $\phi = \sigma^{-1}\alpha^{-1}$.

Representing an embedded graph as a combinatorial map

Let $\theta$ be an embedding of a graph $G$ with $n$ edges into a surface $X$ which is compact, connected, oriented, and without boundary (below we will just call these “oriented surfaces” for short). We can associate a combinatorial map to this topological embedding, which is unique up to isomorphism:

• $D$ is defined as a set containing $2n$ elements, with a pair of distinct darts $e^+,e^- \in D$ for each edge $e \in G$. These darts may be visualized as oriented edges, or alternatively as half-edges (splitting each of the original edges in the middle).

• the collection of edges induces a fixed point-free involution $\alpha$ on $D$, by swapping $e^+$ with $e^-$ for each edge $e \in G$.

• suppose darts are visualized as oriented edges: we will say that a dart $d$ is incident to a vertex $x$ if $x$ is the unique vertex located at the source of $d$. Then every vertex $x\in G$ determines a cyclic ordering of the darts incident to $x$, by considering (say) a counterclockwise-oriented loop around $\theta(x)$. In this way (which relies on the assumption that $X$ is oriented), each vertex determines a cycle of the permutation $\sigma$.

• similarly, we say that a dart $d$ is incident to a face $f$ (i.e., a connected component of $X \setminus \theta(G)$) if $f$ is the unique face appearing to the left of $d$. Then each face $f$ determines a cyclic ordering of darts incident to $f$ (corresponding to a counterclockwise traversal along the perimeter of $f$), and we can combine these disjoint cycles into a single permutation $\phi$.

• if we start at any dart $d \in D$, then apply the permutation $\sigma$ followed by $\alpha$ followed followed by $\phi$, we always end up back at $d$.

Hypermaps and constellations

There are several directions for generalizing the classical definition. A small but useful generalization is to drop the requirement that $\alpha$ be fixed point free, while keeping the requirement that it be an involution (i.e., that $\alpha^2 = id$). This can be seen as allowing the possibility for the graph to include “dangling edges”. In particular, every $\alpha$-orbit has length 2 or 1, with orbits of length 2 representing complete edges and orbits of length 1 representing dangling edges.

As a bigger step, it is possible to drop condition (3) altogether:

Definition

A combinatorial hypermap is a set $D$ equipped with a triple of permutations $(\sigma,\alpha,\phi)$ on $D$ such that:

1. the subgroup $\langle \sigma,\alpha,\phi\rangle$ of $Aut(D)$ generated by the permutations acts transitively on $D$;

2. the composition of the permutations is the identity: $\phi\alpha\sigma = id$.

A combinatorial hypermap gives a representation of a topological embedding of a hypergraph in a oriented surface, but (as noted by Walsh) this is equivalent to an embedding of an ordinary graph equipped with a 2-coloring of its vertices. (Such a graph is necessarily a bipartite graph.) Then, the permutations $\sigma$ and $\alpha$ represent the cycles around the black and white vertices, respectively, while $\phi$ as before represents the faces. Any ordinary map with all black vertices can be seen as a hypermap with a white vertex dividing each edge (thinking of darts as half-edges), and from that perspective, the definition of hypermap simply corresponds to lifting the restriction that white vertices have degree 2.

Both of these generalizations of the standard notion of combinatorial map are studied in the literature on so-called dessins d'enfants, sometimes using the following terminology to distinguish the different cases:

• $\alpha$ is a fixed point free involution : “clean dessin”

• $\alpha$ is an involution : “pre-clean dessin”

• no conditions on $\alpha$ (besides (1) and (2) above): “dessin”

Another line of generalization is to consider an arbitrary number of permutations (rather than only three). This more general notion of hypermap is called a “constellation” in Lando & Zvonkin.

Definition

A k-constellation is a set $D$ equipped with a $k$-tuple of permutations $\alpha_1,\dots,\alpha_k$ on $D$ such that:

1. the subgroup $\langle \alpha_1,\dots,\alpha_k\rangle$ of $Aut(D)$ generated by the permutations acts transitively on $D$;

2. the composition of the permutations is the identity: $\alpha_k\dots\alpha_1 = id$.

Fixed vertex/edge/face degrees

If one adds, say, the condition that

• $\sigma^3 = id$ and $\sigma$ has no fixed points

to the definition of combinatorial map, then the resulting class of permutations represent embeddings of trivalent graphs, i.e., where every vertex has degree 3. Dually, placing the condition that

• $\phi^3 = id$ and $\phi$ has no fixed points

gives a way of representing arbitrary triangulations of oriented surfaces. Analogous to what we saw above in the case of the edge involution $\alpha$, dropping the condition that $\sigma$ or $\phi$ be fixed point free also allows for the possibility of degenerate vertices/faces of degree 1.

More generally, we can say that a map has type $(m,n)$ if the permutations $\sigma$ and $\phi$ have orders $m$ and $n$ respectively (allowing for the possibility that $m = \infty$ or $n = \infty$ in the case where the set of darts is infinite). This algebraic condition translates to the geometric condition that $m$ is the least common multiple of the degrees of the vertices of the map, and $n$ is the least common multiple of the degrees of the faces.

Realizing a combinatorial map as a graph embedded in a Riemann surface

Conversely, any combinatorial map $M = (D,(\sigma,\alpha,\phi))$ can be realized as a graph embedded in a surface, in other words as a topological map. The first explicit algorithm for computing such an embedding was given by Edmonds 1960.

The underlying graph $G(M)$ of $M$ is easy to describe using the “Serre” definition of a graph (as explained here) $G(M) = (H,V,i,s)$. The set of half-edges $H$ and the involution $i$ are just $D$ and $\alpha$, respectively, while the set of vertices $V$ is the set of $\sigma$-orbits, and the function $s : H \to V$ sends any dart to its orbit under $\sigma$.

Some more work is required in order to define a surface $X$ and an embedding of $G(M)$ into $X$. Jones and Singerman 1978 actually proved a stronger result than Edmonds’ algorithm, showing that any combinatorial map (of finite type $(m,n)$) can be realized as a graph embedded in a Riemann surface. As a corollary, this implies that any topological map (on a compact oriented surface without boundary) is isomorphic to some canonical map on a Riemann surface.

Genus of a combinatorial map

The genus $g$ of a combinatorial map $M = (\sigma,\alpha,\phi)$ can be defined directly using the Euler-Poincaré formula,

$$\chi(M) = c(\sigma) - c(\alpha) + c(\phi) = 2-2g$$

where $c(\pi)$ counts the number of cycles in the cyclic decomposition of $\pi$ (i.e., the number of $\pi$-orbits). This definition of genus agrees with the genus of the underlying surface of the embedded graph associated to $M$.

Dual map

Any embedded graph has a dual graph embedded into the same surface, constructed by placing a vertex in the middle of each face, and connecting two vertices whenever the corresponding faces share an edge. This construction is particularly easy to express on combinatorial maps: for any $M = (D,(\sigma,\alpha,\phi))$, the corresponding dual map is defined by $M^* = (D,(\phi^{-1},\alpha^{-1},\sigma^{-1}))$. This operation is clearly an involution (with fixed points, since some maps are self-dual). Moreover, it extends to an operation on hypermaps.

Equivalence with other families of objects

Tetravalent maps with bicolored faces

To any graph $G$ embedded in an oriented surface $X$, one can associate a tetravalent graph $G^m$ embedded in the same surface $X$ by the following construction:

• one vertex $v_e \in G^m$ for every edge $e \in G$;

• one edge $v_{e_1} \sim v_{e_2} \in G^m$ for every ordered pair of edges $e_1,e_2 \in G$ which occur consecutively along the same face in $\theta(G)$.

In graph theory, this is known as the medial graph construction. As with the dual graph construction, though, note that this is only well-defined as an operation on embedded graphs (i.e., topological maps) rather than on abstract graphs: the same graph can have different medial graphs, depending on how it is embedded into a surface. To avoid confusion, we refer to this as the medial map construction.

Two topological maps $M_1$ and $M_2$ have isomorphic medial maps $M_1^m \cong M_2^m$ if and only if they are either isomorphic $M_1 \cong M_2$ or dual $M_1 \cong M_2^*$. To distinguish between duals, one can define a 2-coloring of the faces of the medial map as follows: a face of $M^m$ is colored in black just in case it contains a vertex of $M$, and white otherwise. The construction of the 2-colored medial map thus defines a one-to-one correspondence between general maps and face 2-colored tetravalent maps on oriented surfaces.

Alternating virtual links

Any alternating virtual link (in the sense of virtual knot theory) is naturally represented by a face 2-colored tetravalent map: each ordinary crossing becomes a vertex of degree 4, with faces colored according to the pattern of under/over crossings (virtual crossings appearing in the link diagram disappear when the knot is embedded into the appropriate surface of higher genus). Thus, any alternating virtual link can be encoded by a unique combinatorial map, and vice versa: see Section 4 of Zinn-Justin and Zuber 2004 where they discuss this representation.

The category of oriented maps

In this section we will adopt the more liberal notion of combinatorial map described above, for which the involution $\alpha$ is allowed to have fixed points corresponding to “dangling” edges. We will also sometimes write map as shorthand for combinatorial map in this more liberal sense.

Definition

The category of combinatorial maps $CM$ is defined as follows:

• objects are pairs of a set $D$ together with a triple of permutations $(\sigma,\alpha,\phi)$ on $D$ such that $\langle\sigma,\alpha,\rho\rangle$ acts transitively on $D$ and $\alpha^2 = \phi\alpha\sigma = id$.

• morphisms $(D,(\sigma,\alpha,\phi)) \to (D',(\sigma',\alpha',\phi'))$ are functions $h : D \to D'$ such that $h\sigma = \sigma' h$, $h\alpha = \alpha' h$, and $h\phi = \phi' h$.

The category $CM$ was defined by Jones and Singerman 1978 essentially as above (they call it $AM$ for “algebraic maps”). Specifically, Jones and Singerman take this category to include combinatorial maps in which the involution $\alpha$ may contain fix points.

Proposition

$CM$ is a concrete category, with a faithful functor $U : CM \to Set$ which sends any combinatorial map $(D,(\sigma,\alpha,\phi))$ to its underlying set of darts $D$, and any homomorphism of maps $h : M \to M'$ to a function $h : D \to D'$ between the underlying sets of darts.

Terminal object

We note that the following property of $CM$ relies on allowing maps with dangling edges.

Proposition

The set $1 = \{ * \}$ equipped with the triple of identity permutations $\sigma = \alpha = \phi = id_1$ is a map, and is a terminal object in $CM$.

The oriented cartographic group

(See also article: cartographic group.)

Definition

The oriented cartographic group $\mathcal{C}_2^+$ is the group generated by three elements $\rho_0,\rho_1,\rho_2$ satisfying the relations $\rho_1^2 = \rho_0\rho_1\rho_2 = 1$.

Proposition

The oriented cartographic group is isomorphic to a free product of the integers with the integers modulo 2, $\mathcal{C}_2^+ \cong \mathbb{Z} \star \mathbb{Z}_2$.

Every combinatorial map is a $\mathcal{C}_2^+$-set, i.e., a set equipped with an action of the oriented cartographic group. In fact, $CM$ is just the full subcategory of $\mathcal{C}_2^+Set$ consisting of sets equipped with a transitive action of $\mathcal{C}_2^+$.

Remark

The modular group $PSL_2(\mathbb{Z}) \cong \mathbb{Z}_3 \star \mathbb{Z}_2$ is a quotient of the oriented cartographic group. Sets equipped with a transitive action of $PSL_2(\mathbb{Z})$ are the same thing as trivalent combinatorial maps, which represent trivalent graphs (possibly including degeneracies) embedded in oriented surfaces (or dually, triangulations of oriented surfaces).

For any given map $M$ with underlying set of darts $D$ we will denote the action of the oriented cartographic group by

$$*_M : D \times \mathcal{C}_2^+ \to D,$$

omitting subscripts when clear from context. The fact that $\mathcal{C}_2^+$ acts transitively on $D$ corresponds to the topological condition that the graph represented by $M$ is connected. As we will see, this places strong restrictions on possible morphisms between maps:

Proposition

A morphism $h : M_1 \to M_2$ of combinatorial maps is entirely determined given the image of a single dart $h(d_1) \in D_2$.

Proof

Let $d_1' \in D_1$. By assumption of transitivity, there exists a word $w \in \mathcal{C}_2^+$ such that $d_1' = d_1 *_1 w$. Hence $h(d_1') = h(d_1 *_1 w) = h(d_1) *_2 w$.

Proposition

If $h : M_1 \to M_2$ is a morphism of combinatorial maps and $D_1$ is inhabited, then the underlying function $h : D_1 \to D_2$ is a surjection.

Proof

Let $d_2 \in D_2$. By assumption that $D_1$ is inhabited there exists a $d_1 \in D_1$, and by assumption of transitivity there exists $w \in \mathcal{C}_2^+$ such that $d_2 = h(d_1) *_2 w$. Since $h(d_1) *_2 w = h(d_1 *_1 w)$, the dart $d_1 *_1 w \in D_1$ is in the inverse image of $d_2 \in D_2$.

Rooted maps

Enumeration of maps is an active branch of combinatorics, going back to the work of W. T. Tutte in the 1960s. One of the difficulties with trying to count (combinatorial or topological) maps directly, though, is that they can have non-trivial symmetries, which would need to be accounted for to avoid double-counting. This is why combinatorists typically begin with the easier problem of counting rooted maps, as suggested in this autobiographical account by Tutte:

Having made no progress with the enumeration of these diagrams [(strict triangulations of the plane)] I bethought myself of Cayley’s work on the enumeration of trees. His first successes had been with the rooted trees, in which one vertex is distinguished as the “root”. Perhaps I should root the strict triangulations in some way and try to enumerate the rooted ones. Eventually I decided that the rooting should consist of the choice of a face, edge and vertex, mutually incident….

I am not sure what I would have replied at this stage if I had been asked why I preferred these rooted triangulations to the unrooted ones…. Later I realized that the distinguishing feature and the great advantage of rooted maps is that they have no symmetry. Automorphisms seem to complicate enumerative problems.

(From Chapter 10 of W. T. Tutte, Graph Theory As I Have Known It, Oxford, 1998.)

For a combinatorial map $(D,(\sigma,\alpha,\phi))$, choosing “a face, edge and vertex, mutually incident” is equivalent to choosing a dart $r \in D$: the root vertex, edge, and face can then be computed as the orbits of $r$ under the three permutations. Rooted combinatorial maps may be organized into another category:

Definition

The category of rooted combinatorial maps $CM_\bullet$ is defined as follows:

• objects are pairs of a map $M = (D,(\sigma,\alpha,\phi))$ together with a distinguished dart $r \in D$ called the root.

• morphisms $(M,r) \to (M',r')$ are map morphisms $h : M \to M'$ in $CM$ which preserve the root $h(r) = r'$.

Note that $CM_\bullet$ is equivalent to the comma category $1 \downarrow U$ of the singleton set 1 with the forgetful functor $U : CM \to Set$. Now we have the following basic observations, in line with the above remarks by Tutte:

Proposition

For $M = (D,(\sigma,\alpha,\phi))$ a combinatorial map, the automorphism group $Aut(M)$ is by definition the subgroup of permutations on $D$ which commute with $\sigma$ and $\alpha$ and $\phi$, i.e., the centralizer of $\langle\sigma,\alpha,\phi\rangle$.

Proposition

For $(M,r)$ a rooted combinatorial map, the automorphism group $Aut(M,r)$ is always trivial. In particular, if $h : (M,r) \to (M,r)$ is an endomorphism of $(M,r)$ in the category of rooted maps $CM_\bullet$, then $h$ must be the identity morphism.

Proof

Let $d \in D$ be any dart of $M$. Since the action of $\mathcal{C}_2^+$ is transitive, there is some word $w \in \mathcal{C}_2^+$ such that $d = r * w$, and therefore $h(d) = h(r * w) = h(r) * w = r * w = d$.

Related concepts

• cartographic group

• topological map

• child's drawing

• ribbon graph

References

• J. Edmonds (1960), A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7, 646.

• A. Jacques (1970), Constellations et graphes topologiques, Colloque Math. Soc. Janos Bolyai, 657-672.

• W. T. Tutte. What is a map? In New Directions in Graph Theory (ed. F. Harary), Academic Press, New York, 309-325, 1973.

• W. T. Tutte. Duality and Trinity. In Infinite and Finite Sets (III), Colloq. Math. Soc. Janos Bolyai, vol. 10, 1459-1472, North Holland, Amsterdam, 1975.

• Gareth A. Jones and David Singerman, Theory of Maps on Orientable Surfaces. Proceedings of the London Mathematical Society, 37:273-307, 1978.

• Gareth Jones and David Singerman. Maps, hypermaps, and triangle groups. In The Grothendieck Theory of Dessins d’Enfants, L. Schneps (ed.), London Mathematical Society Lecture Note Series 200, Cambridge University Press, 1994.

• Sergei K. Lando and Alexander K. Zvonkin, Graphs on Surfaces and Their Applications, Springer, 2004.

• Samuel Vidal, Groupe Modulaire et Cartes Combinatoires. Génération et Comptage. PhD Thesis, Université Lille I, France, July 2010. pdf

• Alexander K. Zvonkin, Functional Composition is a Generalized Symmetry, Symmetry: Culture and Science Vol. 21, Nos.1-4, 333-368, 2010. (pdf)

• P. Zinn-Justin and J.-B. Zuber, Matrix Integrals and the Generation and Counting of Virtual Tangles and Links, Journal of Knot Theory and Its Ramifications, 13:03, May 2004. (arXiv)

• Wikipedia page: Combinatorial map